home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group98c.txt / 000146_icon-group-sender _Thu Dec 17 16:33:02 1998.msg < prev    next >
Internet Message Format  |  2000-09-20  |  4KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id QAA26376
  4.     for icon-group-addresses; Thu, 17 Dec 1998 16:32:56 -0700 (MST)
  5. Message-Id: <199812172332.QAA26376@baskerville.CS.Arizona.EDU>
  6. From: "Nevin Liber" <nevin@eviloverlord.com>
  7. To: <icon-group@optima.CS.Arizona.EDU>
  8. Subject: digisort
  9. Date: Thu, 17 Dec 1998 17:18:15 -0600
  10. X-Priority: 3 (Normal)
  11. X-MSMail-Priority: Normal
  12. Importance: Normal
  13. X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3155.0
  14. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  15. Status: RO
  16.  
  17. Ken Walker <mailto:kenneth.walker@sfo.harbinger.com> wrote:
  18.  
  19. > Here is a rather straightforward solution to the problem of
  20. > sorting digits while preserving the sign of an integer.
  21.  
  22. Since ASCII "-" comes before "0" in sort order, there is no need to special
  23. case the minus sign.  Here is a smaller straightforward (IMHO) solution,
  24. which is the same in principle as Ken's, yet differs very widely in the
  25. details:
  26.  
  27.     procedure digisort(i)
  28.  
  29.         local    L
  30.         local    s
  31.  
  32.         L := list()
  33.         every put(L, !i)
  34.  
  35.         s := ""
  36.         every s ||:= !sort(L)
  37.  
  38.         return integer(s)
  39.  
  40.     end
  41.  
  42. 1.  I tend to use the idiom L := list() instead of L := [].
  43.  
  44. 2.  Ken used string scanning to build the list, while I used element
  45. generation.
  46.  
  47. 3.  Ken used the destructive (to a list L1) get(L1) to build the string,
  48. while I used the non-destructive element generation !L1.
  49.  
  50.  
  51.  
  52. > I thought of trying csets, but they discard duplicate digits...
  53.  
  54. digisort() really consists of two subproblems:  counting and sorting.  If
  55. you seperate out the counting, you can use cset() to do the sorting, as in:
  56.  
  57.     procedure digisort(i)
  58.  
  59.         local    T
  60.         local    s
  61.  
  62.         T := table("")
  63.         every s := !i do T[s] ||:= s
  64.  
  65.         s := ""
  66.         every s ||:= T[!cset(i)]
  67.  
  68.         return integer(s)
  69.  
  70.     end
  71.  
  72. T is a table with each digit as a key whose value is a string of that digit
  73. with a length corresponding to the number of times that digit appears in i,
  74. and cset(i) does the sorting.
  75.  
  76.  
  77. If you wanted to make the counting more explicit, you could do something
  78. like:
  79.  
  80.     procedure digisort(i)
  81.  
  82.         local    T
  83.         local    s1
  84.         local    s2
  85.  
  86.         T := table(0)
  87.         every T[!i] +:= 1
  88.  
  89.         s1 := ""
  90.         every s2 := !cset(i) do s1||:= repl(s2, T[s2])
  91.  
  92.         return integer(s1)
  93.  
  94.     end
  95.  
  96.  
  97. If you didn't want to build up a list or a table, you could do the sorting
  98. first and then the counting by multiple passes over (the string of) i, as
  99. in:
  100.  
  101.     procedure digisort(i)
  102.  
  103.         local    s
  104.         local    s1
  105.         local    s2
  106.  
  107.         s := string(i)
  108.         s2 := ""
  109.  
  110.         every s1 := !cset(s) do s ? {
  111.             while tab(find(s1)) do {
  112.                 s2 ||:= move(1)
  113.             }
  114.         }
  115.  
  116.         return integer(s2)
  117.  
  118.     end
  119.  
  120.  
  121. > There should be a solution that is shorter and more obscure;
  122.  
  123. Here you go :-):
  124.  
  125.     procedure digisort(i)
  126.  
  127.         local    s
  128.  
  129.         s := ""
  130.         every s ||:= (i ? (tab(find(!cset(&subject))) & move(1)))
  131.  
  132.         return integer(s)
  133.  
  134.     end
  135.  
  136. You can even replace
  137.  
  138.     cset(&subject)
  139. with
  140.     cset(i)
  141.  
  142. to make it ever-so-slightly shorter, but I think that taking the cset of a
  143. string is ever-so-slightly faster than taking the cset of an integer.  Of
  144. course, one could find parallels between the internal way that cset(s)
  145. converts a string to a cset (I'm guessing by a bucket sort) and the
  146. digisort() algorithm itself...
  147.  
  148. > (You can tell I've been programming too much in C by all the
  149. > semicolons at the end of lines; it also took me a few tries
  150. > to get all the colons before the equals. :-)
  151.  
  152. (And I've been programming too much in MUMPS lately, which is why all my
  153. variables are only one or two letters long. :-))
  154. __
  155.  Nevin ":-)" Liber  <mailto:nliber@nationalsystems.com>  (312) 855-1000 x199
  156.  
  157. National Systems Corporation
  158. 414 North Orleans Street, Suite 501
  159. Chicago, IL 60610-4490
  160. fax: (312) 222-1605
  161. <http://www.nationalsystems.com>
  162.  
  163.